package tree.迭代bfs.剑指;

import java.util.Stack;

/**
 * @author songZiHao
 * @version 1.0.0
 * @ClassName N剑指Offer二叉搜索树的后序遍历序列33.java
 * @Description TODO https://leetcode-cn.com/problems/er-cha-sou-suo-shu-de-hou-xu-bian-li-xu-lie-lcof/
 * @createTime 2021年03月28日 11:29:00
 */
public class N剑指Offer二叉搜索树的后序遍历序列33 {
    /**
     * 1
     * 2     3
     * 4
     */
    public boolean verifyPostorder(int[] postorder) {
        return verify(0, postorder.length - 1, postorder);
    }

    private boolean verify(int start, int end, int[] postorder) {
        if (start >= end) {
            return true;
        }
        //todo 二叉搜索树的 左节点<根节点<右节点，后序遍历的大小为  左节点<右节点>根节点 一直往按照左子树往上找，直到找到右节点
        int p = start;
        while (postorder[p] < postorder[end]) {
            p++;
        }
        int m = p;
        //todo 一直按照右子树往上找 找到根节点
        while (postorder[m] < postorder[end]) {
            m++;
        }
        return p == end && verify(start, m - 1, postorder) && verify(m, end - 1, postorder);
    }

    /**
     * todo https://leetcode-cn.com/problems/er-cha-sou-suo-shu-de-hou-xu-bian-li-xu-lie-lcof/solution/dan-diao-di-zeng-zhan-by-shi-huo-de-xia-tian/
     * 单调栈：
     * 二叉搜索树是left < root < right的，后序遍历的顺序是 left-> right -> root
     * 后序遍历的逆序 root->right->left，这是换了一个方向的先序遍历，从root开始，先遍历右子树，再遍历左子树。怎么做到先root，然后right，最后left呢，只要我们反向遍历数组，这样我们就可以利用单调栈了。
     * <p>
     * todo 如果是按照root->right->left方式进行遍历，那么排序的结果就是 先从小到大，然后到某一个点的时候就是 从大到小了，而这个临界值就是左子树
     */
    public boolean verifyPostorder2(int[] postorder) {
        Stack<Integer> stack = new Stack<>();
        //todo 表示上一个根节点的元素，这里可以把postorder的最后一个元素root看成无穷大节点的左孩子
        int rootVal = Integer.MAX_VALUE;
        //todo 按照逆序进行遍历
        for (int i = postorder.length - 1; i >= 0; i--) {
            //todo 如果大于则不管
            if (postorder[i] > rootVal) {
                return false;
            }
            //todo 如果比小，则一直比较栈中的记录，找到比当前节点小的，作为根节点
            while (!stack.isEmpty() && postorder[i] < stack.peek()) {
                rootVal = stack.pop();
            }

            stack.push(postorder[i]);
        }
        return true;
    }

}
